package zhanyuduilie

import (
	"math"
	"sort"
)

func TopKFrequent(nums []int, k int) []int {
	ans := make([]int, k)
	if k == 1 {
		return nums
	}
	sort.Ints(nums)
	cur := nums[0]
	times := 0
	for i := 0; i < len(nums); i++ {
		if cur == nums[i] {
			times++
		} else {
			JudgeInsert(ans, times)
			times = 1
		}
	}
	return ans
}

func JudgeInsert(nums []int, num int) {
	pla := 0
	minI := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		if minI > nums[i] {
			minI = nums[i]
			pla = i
		}
	}
	if num > minI {
		nums[pla] = num
	}
}

// 继续使用单调队列进行

type MyQueue2 struct {
	queue []int
}

func (m *MyQueue2) Front() int {
	return m.queue[0]
}
func (m *MyQueue2) Back() int {
	return m.queue[len(m.queue)-1]
}
func (m *MyQueue2) IsEmpty() bool {
	return len(m.queue) == 0
}
func (m *MyQueue2) Push(x int) {
	for !m.IsEmpty() && m.Back() < x {
		m.queue = m.queue[:len(m.queue)-1]
	}
	m.queue = append(m.queue, x)
}
func (m *MyQueue2) Pop(x int) {
	if !m.IsEmpty() && m.Front() < x {
		m.queue = m.queue[1:]
	}
}

func TopKFrequent1(nums []int, k int) []int {
	ans := make([]int, 0)
	sort.Ints(nums)
	hash := map[int]int{}
	for i := 0; i < len(nums); i++ {
		hash[nums[i]]++
	}
	list2 := make([]int, 0)
	hash1 := map[int]int{}
	for num, v := range hash {
		hash1[v] = num
		list2 = append(list2, v)
	}
	sort.Slice(list2, func(i, j int) bool {
		return list2[i] > list2[j]
	})
	for i := 0; i < k; i++ {
		a := hash1[list2[i]]
		ans = append(ans, a)
	}
	return ans
}
